from typing import List


class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        m, n = len(board), len(board[0])

        change = True
        while change:
            change = False

            # 寻找可以消除的位置
            remove = [[False] * n for _ in range(m)]
            for i in range(m):
                for j in range(n - 2):
                    if board[i][j] == board[i][j + 1] == board[i][j + 2] != 0:
                        change = True
                        remove[i][j] = remove[i][j + 1] = remove[i][j + 2] = True
            for j in range(n):
                for i in range(m - 2):
                    if board[i][j] == board[i + 1][j] == board[i + 2][j] != 0:
                        change = True
                        remove[i][j] = remove[i + 1][j] = remove[i + 2][j] = True

            # 消除方块并使方块下落
            for j in range(n):
                i2 = m - 1
                i1 = m - 1
                while i1 >= 0 and board[i1][j] != 0:
                    if remove[i1][j] is False:
                        board[i2][j] = board[i1][j]
                        i2 -= 1
                    i1 -= 1

                for i3 in range(i2, -1, -1):
                    board[i3][j] = 0

        return board


if __name__ == "__main__":
    # [[0,0,0,0,0],
    # [0,0,0,0,0],
    # [0,0,0,0,0],
    # [110,0,0,0,114],
    # [210,0,0,0,214],
    # [310,0,0,113,314],
    # [410,0,0,213,414],
    # [610,211,112,313,614],
    # [710,311,412,613,714],
    # [810,411,512,713,1014]]
    print(Solution().candyCrush(board=[
        [110, 5, 112, 113, 114],
        [210, 211, 5, 213, 214],
        [310, 311, 3, 313, 314],
        [410, 411, 412, 5, 414],
        [5, 1, 512, 3, 3],
        [610, 4, 1, 613, 614],
        [710, 1, 2, 713, 714],
        [810, 1, 2, 1, 1],
        [1, 1, 2, 2, 2],
        [4, 1, 4, 4, 1014]]))
